package Algorithm.Recrusion;

// 一个人爬楼梯，每次能爬1->2个台阶，他爬到n层有几种爬法？
public class ClimbStair {
    // 解析：由于每次只能爬两个楼梯，所以要到达n层的方法数为n-1 层和n-2层爬法相加，可以基于此逻辑递归
    // 逻辑fn(n) = fn(n - 1) + fn(n - 2), f(1) = 1, f(2) = 2
    public static int climbStair(int n) {
        if(n == 1){
            return 1;
        } else if(n == 2){
            return 2;
        } else {
            return climbStair(n-1) + climbStair(n-2);
        }
    }
    public static void main(String[] args) {
        System.out.println(climbStair(3));
    }
}
